package com.maltys.dp.backpack;

import java.util.Arrays;

/**
 * @author malty
 */
public class PartitionEqualSubsetSum {
    public static void main(String[] args) {
        PartitionEqualSubsetSum subSet = new PartitionEqualSubsetSum();
        boolean canPartition = subSet.canPartition(new int[]{3,3,3,4,5});
        System.out.println(canPartition);
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        int[][] dp = new int[nums.length][sum / 2 + 1];

        for (int i = nums[0]; i <= sum / 2; i++) {
            dp[0][i] = nums[0];
        }
        System.out.println(Arrays.toString(dp[0]));
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= sum / 2; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - nums[i]] + nums[i]);
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[nums.length - 1][sum / 2] == sum / 2;
    }
}
